import java.util.ArrayList;
import java.util.List;

// 没有重复项数字的全排列
// 测试链接 : https://leetcode.cn/problems/permutations/
public class Permutations {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        func(nums,0,ans);
        return ans;
    }

    public void func(int[] nums, int pos, List<List<Integer>> ans ){
        if(pos == nums.length){
            ArrayList<Integer> list = new ArrayList<>();
            for(int temp : nums){
                list.add(temp);
            }
            ans.add(list);
        }else{
            for(int next = pos; next < nums.length; next++){
                swap(nums, pos, next);
                func(nums, pos+1 ,ans);
                swap(nums, pos, next);

            }
        }
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
